import java.util.Arrays;
import java.util.Stack;

public class Sort {
    //插入排序
    public static void insertionSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0;j--){
                if (tmp < array[j]){
                    array[j+1] = array[j];
                }else break;
            }
            array[j+1] = tmp;
        }
    }
    //希尔排序
    public static void shell(int[] array,int group){
        for (int i = group;i < array.length;i += 1){
            int tmp = array[i];
            int j = i-group;
            for (;j >= 0;j -= group) {
                if (tmp < array[j]){
                    array[j+group] = array[j];
                }else break;
            }
            array[j+group] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int group =array.length;
        //预排序
        while (group > 1){
            shell(array,group);
            group /= 2;
        }
        shell(array,1);
    }

    //选择排序
    public static void selectSort(int[] array){
        for (int i = 0;i < array.length-1; i++){
            int index = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[index] > array[j])
                    index = j;
            }
            int tmp = array[i];
            array[i] = array[index];
            array[index] = tmp;
        }
    }

    //堆排序
    public static void creationHeap(int[] array) {
        for (int parent = (array.length-1-1)/2;parent >= 0;parent--)
            shiftDown(array,parent,array.length);
    }
    public static void shiftDown(int[] array,int parent,int len){
        int child = parent *2 +1;
        while (child < len){
            //获取左右子数最大值的下标
            if(child+1 < len && (array[child] < array[child+1])){
                child++;
            }
            if(array[child] > array[parent]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
    public static void heapSort(int[] array){
        int end = array.length -1;
        while (end > 0){
            int tmp = array[end];
            array[end] = array[0];
            array[0] = tmp;
            shiftDown(array,0,end);
            end--;
        }
    }

    //快速排序
    public static void quickSort(int[] array){
        quick(array,0, array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        int pivot = partiton(array,start,end);
        quick(array,start,pivot-1);// 递归左边
        quick(array,pivot+1,end);// 递归右边
    }
    // 分割
    private static int partiton(int[] array,int start,int end){
        int tmp = array[start];
        while(start < end){
            while(start < end && array[end] >= tmp){
                end--;
            }
            // 此时 end 下标 元素的值 是 小于 tmp的。
            array[start] = array[end];
            while(start<end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    public static void main2(String[] args) {
        int[] array = {6,1,2,7,9,3,4,5,10,8};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static  void quickSort1(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partiton(array,left,right);
        if (pivot > left+1){
            stack.push(left);
            stack.push(pivot -1);
        }
        if (pivot < right -1 ){
            stack.push(pivot+1);
            stack.push(right);
        }
        while (! stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partiton(array,left,right);
            if(pivot > left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot < right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    //归并排序
    public static int[] mergeSort(int[] array){
        if (array == null)
            return array;
        mergeSortFunc(array,0,array.length-1);
        return array;
    }
    public static void mergeSortFunc(int[] array,int low,int high){
        if (low >= high)
            return;
        int mid = low + ((high-low) >>> 1);
        mergeSortFunc(array,low,mid);//左
        mergeSortFunc(array,mid+1,high);//右
        merge(array,low,mid,high);
    }
    public static void merge(int[] array,int low,int mid,int high){
        int[] arr = new int[high-low+1];
        int start1 = low;
        int end1 = mid;
        int start2 = mid+1;
        int end2 = high;
        int i = 0;
        while (start1 <= end1 && start2 <= end2){
            if(array[start1] > array[start2]){
                arr[i++] = array[start2++];
            }else{
                arr[i++] = array[start1++];
            }
        }
        while(start1 <= end1){
            arr[i++] = array[start1++];
        }
        while(start2 <= end2){
            arr[i++] = array[start2++];
        }
        for (int j = 0; j < arr.length; j++) {
            array[low++] = arr[j];
        }
    }

    //
    public static void countingSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal){
                maxVal = array[i];
            }
            if(array[i] < minVal){
                minVal =array[i];
            }
        }
        // 当循环结束，获得了 数据的最大值 和 最小值
        // 可以确定计数数组的容量
        int[] count = new int[maxVal -minVal +1];
        for (int i = 0; i < array.length; i++) {
            // 提高空间利用率
            count[ array[i] - minVal ]++;
        }
        // 此时，计数数组 已经把array数组当中，每个元素的出现次数统计好了
        // 接下来，只需要遍历计数数组，把 数据 覆写 到 array当中。
        int indexArray = 0; // 用于遍历 array数组，标记 覆写的位置。
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                // 这里一定要加上减去minVal，因为 下标 i 不一定 在 array 数组中出现过。
                array[indexArray++] = i + minVal;// 拿出来的时候，记得将减去的值加上
                // indexArray++;
                count[i]--;
            }
        }
    }

}




























